{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reachable Nodes In Subdivided Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reachableNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #细分图中的可到达节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个无向图（<strong>原始图</strong>），图中有 <code>n</code> 个节点，编号从 <code>0</code> 到 <code>n - 1</code> 。你决定将图中的每条边 <strong>细分</strong> 为一条节点链，每条边之间的新节点数各不相同。</p>\n",
    "\n",
    "<p>图用由边组成的二维数组 <code>edges</code> 表示，其中&nbsp;<code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>, cnt<sub>i</sub>]</code> 表示原始图中节点&nbsp;<code>u<sub>i</sub></code> 和&nbsp;<code>v<sub>i</sub></code> 之间存在一条边，<code>cnt<sub>i</sub></code> 是将边 <strong>细分</strong> 后的新节点总数。注意，<code>cnt<sub>i</sub> == 0</code> 表示边不可细分。</p>\n",
    "\n",
    "<p>要 <strong>细分</strong> 边 <code>[ui, vi]</code> ，需要将其替换为 <code>(cnt<sub>i</sub> + 1)</code> 条新边，和&nbsp;<code>cnt<sub>i</sub></code> 个新节点。新节点为 <code>x<sub>1</sub></code>, <code>x<sub>2</sub></code>, ..., <code>x<sub>cnt<sub>i</sub></sub></code> ，新边为 <code>[u<sub>i</sub>, x<sub>1</sub>]</code>, <code>[x<sub>1</sub>, x<sub>2</sub>]</code>, <code>[x<sub>2</sub>, x<sub>3</sub>]</code>, ..., <code>[x<sub>cnt<sub>i</sub>-1</sub>, x<sub>cnt<sub>i</sub></sub>]</code>, <code>[x<sub>cnt<sub>i</sub></sub>, v<sub>i</sub>]</code> 。</p>\n",
    "\n",
    "<p>现在得到一个&nbsp;<strong>新的细分图</strong> ，请你计算从节点 <code>0</code> 出发，可以到达多少个节点？如果节点间距离是 <code>maxMoves</code> 或更少，则视为 <strong>可以到达</strong> 。</p>\n",
    "\n",
    "<p>给你原始图和 <code>maxMoves</code> ，返回 <em>新的细分图中从节点 <code>0</code> 出发</em><strong><em> 可到达的节点数</em></strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/08/01/origfinal.png\" style=\"height: 247px; width: 600px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3\n",
    "<strong>输出：</strong>13\n",
    "<strong>解释：</strong>边的细分情况如上图所示。\n",
    "可以到达的节点已经用黄色标注出来。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4\n",
    "<strong>输出：</strong>23\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= min(n * (n - 1) / 2, 10<sup>4</sup>)</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub> &lt; v<sub>i</sub> &lt; n</code></li>\n",
    "\t<li>图中 <strong>不存在平行边</strong></li>\n",
    "\t<li><code>0 &lt;= cnt<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= maxMoves &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 3000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reachable-nodes-in-subdivided-graph](https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reachable-nodes-in-subdivided-graph](https://leetcode.cn/problems/reachable-nodes-in-subdivided-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,10],[0,2,1],[1,2,2]]\\n6\\n3', '[[0,1,4],[1,2,6],[0,2,8],[1,3,1]]\\n10\\n4', '[[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]]\\n17\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b, w in edges:\n",
    "            g[a].append((b,w))\n",
    "            g[b].append((a,w))\n",
    "        dist = [float('inf')] * n \n",
    "        def dijk(s, dist):\n",
    "            dist[s] = 0\n",
    "            vis = [0] * n \n",
    "            Q = [(dist[s], s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if vis[u]:\n",
    "                    continue \n",
    "                vis[u] = 1\n",
    "                if d > maxMoves:\n",
    "                    continue\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w + 1:\n",
    "                        dist[v] = dist[u] + w + 1\n",
    "                        heapq.heappush(Q,(dist[v], v))\n",
    "        dijk(0, dist) \n",
    "        ans = 0\n",
    "        for a, b, w in edges:\n",
    "            da = max(maxMoves - dist[a], 0)\n",
    "            db = max(maxMoves - dist[b], 0)\n",
    "            ans += min(da + db, w) \n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        d = [1000000000 for _ in range(n)]\n",
    "        d[0] = 0\n",
    "        maps = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].append((edge[1],edge[2]))\n",
    "            maps[edge[1]].append((edge[0],edge[2]))\n",
    "        q = [(0,0)]\n",
    "        ans = 1\n",
    "        while q:\n",
    "            now = heapq.heappop(q)\n",
    "            for y in maps[now[1]]:\n",
    "                temp = now[0] + y[1]\n",
    "                if temp <= maxMoves:\n",
    "                    if temp < d[y[0]]:\n",
    "                        d[y[0]] = temp + 1\n",
    "                        heapq.heappush(q,(d[y[0]],y[0]))\n",
    "        ans = sum(c <= maxMoves for c in d)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - d[x], 0)\n",
    "            b = max(maxMoves - d[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b, w in edges:\n",
    "            g[a].append((b,w))\n",
    "            g[b].append((a,w))\n",
    "        dist = [float('inf')] * n \n",
    "        def dijk(s, dist):\n",
    "            dist[s] = 0\n",
    "            vis = [0] * n \n",
    "            Q = [(dist[s], s)]\n",
    "            while Q:\n",
    "                d, u = heapq.heappop(Q)\n",
    "                if vis[u]:\n",
    "                    continue \n",
    "                vis[u] = 1\n",
    "                for v, w in g[u]:\n",
    "                    if dist[v] > dist[u] + w + 1:\n",
    "                        dist[v] = dist[u] + w + 1\n",
    "                        heapq.heappush(Q,(dist[v], v))\n",
    "        dijk(0, dist) \n",
    "        ans = 0\n",
    "        for a, b, w in edges:\n",
    "            da = max(maxMoves - dist[a], 0)\n",
    "            db = max(maxMoves - dist[b], 0)\n",
    "            ans += min(da + db, w) \n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        d = [1000000000 for _ in range(n)]\n",
    "        d[0] = 0\n",
    "        maps = {_:[] for _ in range(n)}\n",
    "        for edge in edges:\n",
    "            maps[edge[0]].append((edge[1],edge[2]))\n",
    "            maps[edge[1]].append((edge[0],edge[2]))\n",
    "        q = [(0,0)]\n",
    "        ans = 1\n",
    "        while q:\n",
    "            now = heapq.heappop(q)\n",
    "            for y in maps[now[1]]:\n",
    "                temp = now[0] + y[1]\n",
    "                if temp < d[y[0]]:\n",
    "                    d[y[0]] = temp + 1\n",
    "                    heapq.heappush(q,(d[y[0]],y[0]))\n",
    "        ans = sum(c <= maxMoves for c in d)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - d[x], 0)\n",
    "            b = max(maxMoves - d[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist) # 这里首先统计出来不是边上的节点的个数\n",
    "        # 太妙了\n",
    "        for u, v, cnt in edges:\n",
    "            # 这里计算u和v之间的节点的个数，排除了u和v本身，我们考虑任何一条边，maxMoves -dist[u] 和0取最大值，如果\n",
    "            # dist[u] > maxMoves则不用计算，为0\n",
    "            # dist[u] < maxMoves则意味着有maxMoves - dist[u]的节点都会被计算进去，但是如果maxMoves远远大于dist[u]呢？关键我们最后取了和cnt对比的最小值\n",
    "            # 可以确保只计算uv之间的节点数\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        #print(f'g:{g}')\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x],考虑在这种情况，一个节点是有可能重复进入h队列的，\n",
    "            # 比如一开始的时候被最近的节点更新了距离，然后另一个最近的节点通过另一个路径又更新了同一个点，就有可能出现同一个节点但是距离不同的情况再队列里，这个时候d > dist[x]其实是可以放弃的\n",
    "            # print(f'dist:{dist},d:{d},x:{x},h:{h}')\n",
    "            # if d > dist[x]:\n",
    "            #     continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans \n",
    "    #Dijkstra 算法模板\n",
    "\n",
    "    def dijkstra(self, g, start) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]: continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt \n",
    "                if new_d < dist[y]: \n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, graph: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        import heapq\n",
    "\n",
    "        dist = [float('inf')] * len(graph)\n",
    "        dist[start] = 0\n",
    "        que = []\n",
    "        # 建最小堆\n",
    "        heapq.heappush(que, (0, start))\n",
    "        while len(que) > 0:\n",
    "            cost, node = heapq.heappop(que)\n",
    "            if dist[node] < cost:\n",
    "                continue\n",
    "            for new_node, weight in graph[node]:\n",
    "                next_cost = cost + weight\n",
    "                if dist[new_node] > next_cost:\n",
    "                    dist[new_node] = next_cost\n",
    "                    heapq.heappush(que, (next_cost, new_node))\n",
    "        return dist\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    # Dijkstra 算法模板\n",
    "    def dijkstra(self, g, start) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h: \n",
    "            d, x = heappop(h) # 小顶堆，存(d, i)从start到节点i的最短距离是d\n",
    "            # d, x = h.popleft()\n",
    "            # if d > dist[x]: continue # 避免重复访问\n",
    "            for y, wt in g[x]: # 遍历新的节点\n",
    "                new_d = dist[x] + wt # 最短路更新\n",
    "                if new_d < dist[y]: \n",
    "                    dist[y] = new_d # 判断是否更新\n",
    "                    heappush(h, (new_d, y)) # 更新后入堆\n",
    "            \n",
    "        return dist "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x]\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            graph[u].append((v, cnt+1))\n",
    "            graph[v].append((u, cnt+1))\n",
    "\n",
    "        # dijsktra\n",
    "        distances = [float(\"inf\")] * n\n",
    "        distances[0] = 0\n",
    "        hq = [(0, 0)]\n",
    "        while hq:\n",
    "            distance, x = heapq.heappop(hq)\n",
    "            if distance > distances[x]:\n",
    "                continue\n",
    "            for y, weight in graph[x]:\n",
    "                new_distance = distances[x] + weight\n",
    "                if new_distance < distances[y]:\n",
    "                    distances[y] = new_distance\n",
    "                    heapq.heappush(hq, (new_distance, y))\n",
    "\n",
    "        res = sum(distance <= maxMoves for distance in distances)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - distances[u], 0)\n",
    "            b = max(maxMoves - distances[v], 0)\n",
    "            res += min(a + b, cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        dist = self.dijkstra(g, 0)\n",
    "        ans = sum(d <= maxMoves for d in dist) # 这里首先统计出来不是边上的节点的个数\n",
    "        # 太妙了\n",
    "        for u, v, cnt in edges:\n",
    "            # 这里计算u和v之间的节点的个数，排除了u和v本身，我们考虑任何一条边，maxMoves -dist[u] 和0取最大值，如果\n",
    "            # dist[u] > maxMoves则不用计算，为0\n",
    "            # dist[u] < maxMoves则意味着有maxMoves - dist[u]的节点都会被计算进去，但是如果maxMoves远远大于dist[u]呢？关键我们最后取了和cnt对比的最小值\n",
    "            # 可以确保只计算uv之间的节点数\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n",
    "        \n",
    "    def dijkstra(self,g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        #print(f'g:{g}')\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            # 什么情况下会出现d > dist[x],考虑在这种情况，一个节点是有可能重复进入h队列的，\n",
    "            # 比如一开始的时候被最近的节点更新了距离，然后另一个最近的节点通过另一个路径又更新了同一个点，就有可能出现同一个节点但是距离不同的情况再队列里，这个时候d > dist[x]其实是可以放弃的，快速失败\n",
    "            # print(f'dist:{dist},d:{d},x:{x},h:{h}')\n",
    "            # 这里是一个剪枝，快速失败\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 从节点 0 出发 可到达的节点数\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x,y,cnt in edges:\n",
    "            g[x].append((y,cnt+1))\n",
    "            g[y].append((x,cnt+1))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        start = 0\n",
    "        hq = [(0,start)]\n",
    "        while hq:\n",
    "            w1,x = heapq.heappop(hq)\n",
    "            if w1 > dist[x]:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                w = w1 + w2\n",
    "                if w < dist[y]:\n",
    "                    dist[y] = w\n",
    "                    heapq.heappush(hq,(w,y))\n",
    "        ans = 0\n",
    "        sum(d <= maxMoves for d in dist)\n",
    "        for x in range(n):\n",
    "            if dist[x] <= maxMoves:\n",
    "                ans += 1\n",
    "        print(ans)\n",
    "        for x,y,w in edges:\n",
    "            # 如果dist[x]>maxMoves,则为负,取0\n",
    "            a = max(maxMoves - dist[x],0) #如果从x还可以走a步\n",
    "            b = max(maxMoves - dist[y],0) #如果从y出发还可以走步\n",
    "            ans += min(a+b,w)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 无向图，邻接表 edges[i,j,k]， k表示将边(i,j)分出的新的节点数\n",
    "        # 计算从节点0出发，可到达多少个新节点：最大移动距离： maxMoves\n",
    "        g = [[] for _ in range(n)] # 建图， 边权为cnt+1\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dist = self.dijkstra(g, 0) # dist存放从0出发到各个节点的最短路\n",
    "        ans = sum(d <= maxMoves for d in dist) # 可以在maxMoves不内到达的点的个数\n",
    "        for u, v, cnt in edges: # 每条边上的新节点\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans \n",
    "    #Dijkstra 算法模板\n",
    "\n",
    "\n",
    "    # 加权有向图，单源最短路， 返回dist[i]从0出发到节点i的最短路权重和\n",
    "    def dijkstra(self, g:List[List[Tuple[int]]], start:int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)] # 堆代替deque\n",
    "        while h:\n",
    "            d, x = heappop(h) # \n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]: # 点x到y的距离：wt\n",
    "                new_d = dist[x] + wt \n",
    "                if new_d < dist[y]: # 新的距离更小，更具路径\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        \n",
    "        dis = [inf] * n\n",
    "        dis[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if dis[x] < d:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                if dis[x] + wt < dis[y]:\n",
    "                    dis[y] = dis[x] + wt\n",
    "                    heappush(h, (dis[y], y))\n",
    "        ans = sum(maxMoves >= d for d in dis)\n",
    "        for x, y, cnt in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c + 1])\n",
    "            graph[b].append([a, c + 1])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        res = 0\n",
    "        for a, b, c in edges:\n",
    "            res += min(c, max(maxMoves - dis[a], 0) + max(maxMoves - dis[b], 0))\n",
    "        for node in range(n):\n",
    "            if dis[node] <= maxMoves:\n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 从节点 0 出发 可到达的节点数\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x,y,cnt in edges:\n",
    "            g[x].append((y,cnt+1))\n",
    "            g[y].append((x,cnt+1))\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        start = 0\n",
    "        hq = [(0,start)]\n",
    "        while hq:\n",
    "            w1,x = heapq.heappop(hq)\n",
    "            if w1 > dist[x]:\n",
    "                continue\n",
    "            for y,w2 in g[x]:\n",
    "                w = w1 + w2\n",
    "                if w < dist[y]:\n",
    "                    dist[y] = w\n",
    "                    heapq.heappush(hq,(w,y))\n",
    "        ans = 0\n",
    "        # sum(d <= maxMoves for d in dist)\n",
    "        for x in range(n):# 可以在 maxMoves 步内到达的点的个数\n",
    "            if dist[x] <= maxMoves:\n",
    "                ans += 1\n",
    "        print(ans)\n",
    "        for x,y,w in edges:\n",
    "            # 如果dist[x]>maxMoves,则为负,取0\n",
    "            a = max(maxMoves - dist[x],0) #如果从x还可以走a步\n",
    "            b = max(maxMoves - dist[y],0) #如果从y出发还可以走步\n",
    "            ans += min(a+b,w)# 这条边上可以到达的节点数\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            ans+=min(farx+fary,w)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            if farx>=w+1-fary:\n",
    "                ans-=farx+fary-w\n",
    "            ans+=farx+fary\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        dist = self.dijkstra(g, 0)  # 从 0 出发的最短路\n",
    "\n",
    "        ans = sum(d <= maxMoves for d in dist)  # 可以在 maxMoves 步内到达的点的个数\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            ans += min(a + b, cnt)  # 这条边上可以到达的节点数\n",
    "        return ans\n",
    "\n",
    "    # Dijkstra 算法模板\n",
    "    # 返回从 start 到每个点的最短路\n",
    "    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List[int]:\n",
    "        dist = [inf] * len(g)\n",
    "        dist[start] = 0\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                new_d = dist[x] + wt\n",
    "                if new_d < dist[y]:\n",
    "                    dist[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w + 1))\n",
    "            g[y].append((x, w + 1))\n",
    "\n",
    "        dis = [0] + [inf] * (n - 1)\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            d, x = heappop(q)\n",
    "            if d > dis[x] : continue\n",
    "            for y, w in g[x]:\n",
    "                nd = dis[x] + w\n",
    "                if nd < dis[y]:\n",
    "                    dis[y] = nd \n",
    "                    heappush(q, (nd, y))\n",
    "\n",
    "        print(dis)\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, w)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "                # if abs(dist[u]-dist[v])==1+cnt:\n",
    "                #     total += cnt\n",
    "                # else:\n",
    "                #     total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            graph[u].append((v, nodes+1))\n",
    "            graph[v].append((u, nodes+1))\n",
    "        \n",
    "        dist = [inf]*n\n",
    "        dist[0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            dst, u = q.pop(0)\n",
    "            if dst > dist[u]:\n",
    "                continue\n",
    "            for v, distance in graph[u]:\n",
    "                if dist[u]+distance < dist[v]:\n",
    "                    dist[v] = dist[u]+distance\n",
    "                    q.append((dist[v], v))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dist[i] <=maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, edge in edges:\n",
    "            t1 = max(0, maxMoves-dist[u])\n",
    "            t2 = max(0, maxMoves-dist[v])\n",
    "            ans += min(edge, t1+t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for a, b, cnt in edges:\n",
    "            g[a][b] = g[b][a] = cnt + 1\n",
    "        # 0到其他点的距离\n",
    "        dist = [0] + [float('inf')] * (n - 1)\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            a_cnt, a = heappop(h)\n",
    "            if a_cnt > maxMoves:\n",
    "                break\n",
    "            for b, b_cnt in g[a].items():\n",
    "                if a_cnt + b_cnt < dist[b]:\n",
    "                    heappush(h, (a_cnt + b_cnt, b))\n",
    "                    dist[b] = a_cnt + b_cnt\n",
    "            # print(a, dist)\n",
    "        ans = sum(1 for c in dist if c <= maxMoves)\n",
    "        # print(dist)\n",
    "        # 考虑可达的细分结点\n",
    "        for a, b, cnt in edges:\n",
    "            cnt_a = max(0, maxMoves - dist[a])\n",
    "            cnt_b = max(0, maxMoves - dist[b])\n",
    "            cnt = min(cnt, cnt_a + cnt_b)\n",
    "            ans += cnt\n",
    "            # print(a, b, cnt_a, cnt_b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        q = [(0, 0)]\n",
    "        dist = [0] + [inf] * n\n",
    "        while q:\n",
    "            d, u = heappop(q)\n",
    "            for v, cnt in g[u]:\n",
    "                if (t := d + cnt) < dist[v]:\n",
    "                    dist[v] = t\n",
    "                    q.append((t, v))\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = min(cnt, max(0, maxMoves - dist[u]))\n",
    "            b = min(cnt, max(0, maxMoves - dist[v]))\n",
    "            ans += min(cnt, a + b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        count = 0\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if cost > maxMoves:\n",
    "                break\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            count += 1\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y, w+1))\n",
    "            g[y].append((x, w+1))\n",
    "\n",
    "        dis = self.dijkstra(g, 0)\n",
    "\n",
    "        res = 0\n",
    "        for d in dis:\n",
    "            if d<=maxMoves:\n",
    "                res += 1\n",
    "        \n",
    "        for u, v, w in edges:\n",
    "            a = max(maxMoves-dis[u], 0) \n",
    "            b = max(maxMoves-dis[v], 0)\n",
    "            res += min(a+b, w)\n",
    "        return res\n",
    "    # Dijkstra算法模版\n",
    "    # 返回从stat到每个点的最短路\n",
    "    def dijkstra(self, g, stat):\n",
    "        dis = [inf]*len(g)\n",
    "        dis[stat] = 0\n",
    "        h = [(0, stat)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d>dis[x]:\n",
    "                continue\n",
    "            for y, w in g[x]:\n",
    "                new_d = dis[x] + w\n",
    "                if new_d<dis[y]:\n",
    "                    dis[y] = new_d\n",
    "                    heappush(h, (new_d, y))\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        dis = [inf] * n\n",
    "        dis[0] = 0\n",
    "        h = [(0, 0)]\n",
    "        while h:\n",
    "            d, x = heappop(h)\n",
    "            if d > dis[x]:\n",
    "                continue\n",
    "            for y, wt in g[x]:\n",
    "                if dis[x] + wt < dis[y]:\n",
    "                    dis[y] = dis[x] + wt\n",
    "                    heappush(h, (dis[y], y))\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dis[u], 0)\n",
    "            b = max(maxMoves - dis[v], 0)\n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "        q = [(0, 0)]\n",
    "        dist = [0] + [inf] * n\n",
    "        while q:\n",
    "            d, u = heappop(q)\n",
    "            for v, cnt in g[u]:\n",
    "                if (t := d + cnt) < dist[v]:\n",
    "                    dist[v] = t\n",
    "                    q.append((t, v))\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for u, v, cnt in edges:\n",
    "            a = min(cnt, max(0, maxMoves - dist[u]))\n",
    "            b = min(cnt, max(0, maxMoves - dist[v]))\n",
    "            ans += min(cnt, a + b)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, w in edges:\n",
    "            g[x].append((y, w + 1))\n",
    "            g[y].append((x, w + 1))\n",
    "\n",
    "        dis = [0] + [inf] * (n - 1)\n",
    "        vis = [False] * n \n",
    "        while True:\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x < 0 or dis[i] < dis[x]):\n",
    "                    x = i \n",
    "            if x == -1: break\n",
    "            vis[x] = True\n",
    "            for y, w in g[x]:\n",
    "                if dis[x] + w < dis[y]:\n",
    "                    dis[y] = dis[x] + w\n",
    "\n",
    "        print(dis)\n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "\n",
    "        for x, y, w in edges:\n",
    "            a = max(maxMoves - dis[x], 0)\n",
    "            b = max(maxMoves - dis[y], 0)\n",
    "            ans += min(a + b, w)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import sys\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: [[int]], maxMoves: int, n: int) -> int:\n",
    "\n",
    "        dct = defaultdict(dict)\n",
    "        for a, b, p in edges:  # flights=[ [src,dst, cost] ]\n",
    "            dct[a][b] = p+1\n",
    "            dct[b][a] = p + 1\n",
    "\n",
    "        visit = [sys.maxsize] * n  # 设置已经访问过的节点的最小距离\n",
    "        stack = [[0, 0]]  # 最短路径，当前位置，途径点数目\n",
    "        heapq.heapify(stack)\n",
    "        while stack:\n",
    "            cost, pos = heapq.heappop(stack)\n",
    "#            print(cost,pos)\n",
    "\n",
    "            if cost >= visit[pos]:  # 途径点个数超过以前访问该节点时候的途经点个数，或者途径点的个数已经超过k， 防止重复访问\n",
    "                continue\n",
    "\n",
    "            visit[pos]=min(visit[pos],cost)\n",
    "            for nex in dct[pos]:\n",
    "                if cost + dct[pos][nex]<=maxMoves:\n",
    "                    heapq.heappush(stack, [cost + dct[pos][nex], nex])  # 找到所有下一个可以到达的节点， 计算cost和途经点个数\n",
    "\n",
    "#        print(visit)\n",
    "\n",
    "        tot=0\n",
    "        for xx,yy,points in edges:\n",
    "            fromx=max(maxMoves-visit[xx],0)\n",
    "            fromy=max(maxMoves-visit[yy],0)\n",
    "            cover=min(fromx+fromy,dct[xx][yy]-1)\n",
    "            tot+=cover\n",
    "#            print(xx,yy,fromx,fromy,cover)\n",
    "\n",
    "        for i in range(n):\n",
    "            if visit[i]<=maxMoves: tot+=1\n",
    "\n",
    "        return tot\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        # 2. O(kE) run SPFA\n",
    "        dist = self.SPFA(0, g)\n",
    "\n",
    "        # 3. find reachable vertices by traversing all the vertices\n",
    "        ans = sum(d <= maxMoves for d in dist)  # reachable original vertices\n",
    "        for u, v, cnt in edges:\n",
    "            u_cnt = max(0, maxMoves - dist[u])  # reachable from vertex u on edge u-v\n",
    "            v_cnt = max(0, maxMoves - dist[v]) # reachable from vertex v on edge u-v\n",
    "            ans += min(cnt, u_cnt + v_cnt)  # take intersection of two sets\n",
    "        return ans\n",
    "\n",
    "    def SPFA(self, start_node: int, g: List[List[int]]) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                if not in_queue[v]:\n",
    "                    queue.append(v)\n",
    "                    in_queue[v] = True\n",
    "        \n",
    "        n = len(g)\n",
    "        dist = [math.inf] * n\n",
    "        dist[start_node] = 0\n",
    "        in_queue = [False] * n\n",
    "        queue = deque([start_node])\n",
    "        in_queue[start_node] = True\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            in_queue[u] = False \n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 1. O(V+E) build adjacency list of undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))\n",
    "\n",
    "        # 2. O((V+E)logV) run heap-optimized Dijkstra's algorithm\n",
    "        dist = self.Dijkstra(0, g)\n",
    "\n",
    "        # 3. find reachable vertices by traversing all the vertices\n",
    "        ans = sum(d <= maxMoves for d in dist)  # reachable original vertices\n",
    "        for u, v, cnt in edges:\n",
    "            u_cnt = max(0, maxMoves - dist[u])  # reachable from vertex u on edge u-v\n",
    "            v_cnt = max(0, maxMoves - dist[v]) # reachable from vertex v on edge u-v\n",
    "            ans += min(cnt, u_cnt + v_cnt)  # take intersection of two sets\n",
    "        return ans\n",
    "\n",
    "    def Dijkstra(self, start_node: int, g: List[List[int]]) -> List[int]:\n",
    "        def relax(u: int, v: int, w: int) -> None:\n",
    "            if dist[v] > (d := dist[u] + w):\n",
    "                dist[v] = d \n",
    "                heapq.heappush(pq, (d, v))\n",
    "\n",
    "        n = len(g)\n",
    "        dist = [math.inf] * n  \n",
    "        dist[start_node] = 0 \n",
    "        pq = [(0, start_node)]  # min-heap\n",
    "        while pq:\n",
    "            d, u = heapq.heappop(pq)\n",
    "            if d > dist[u]:    \n",
    "                continue\n",
    "    \n",
    "            for v, w in g[u]:\n",
    "                relax(u, v, w)\n",
    "        return dist\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "原来的边可以新增节点？\n",
    "细分后。。。替换成cnt+1条边，共cnt+2个节点\n",
    "乍一看，需要维护到达每个新节点的最短距离\n",
    "\n",
    "是一个非常复杂的图\n",
    "朴素的bfs跑不动\n",
    "所以，最好不要考虑新增的节点，一旦考虑连建图都见不出来了\n",
    "修改边权跑dij，跑完后遍历每条边，计算这些边上有多少可达节点\n",
    "稠密图，用n^2算法\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g=[[]*n for _ in range(n)]\n",
    "        for x,y,w in edges:\n",
    "            g[x].append((y,w+1))\n",
    "            g[y].append((x,w+1))\n",
    "        dis=[inf]*n\n",
    "        vis=[False]*n\n",
    "        dis[0]=0\n",
    "        #不能用bfs了，悲\n",
    "        '''\n",
    "        while True:\n",
    "            mn=inf\n",
    "            for i in range(n):\n",
    "                if dis[i]<mn and not vis[i]:\n",
    "                    mn=dis[i]\n",
    "                    x=i\n",
    "            if mn==inf:\n",
    "                break\n",
    "            #将与x相邻的边松弛\n",
    "            vis[x]=True\n",
    "            for y,w in g[x]:\n",
    "                if dis[y]>dis[x]+w:\n",
    "                    dis[y]=dis[x]+w\n",
    "        '''\n",
    "        h=[(0,0)]\n",
    "        while h:\n",
    "            d,x=heappop(h)  \n",
    "            if d>dis[x]:\n",
    "                continue #因为同一个点会多次入堆\n",
    "            for y,w in g[x]:\n",
    "                if dis[x]+w<dis[y]:\n",
    "                    dis[y]=dis[x]+w\n",
    "                    heappush(h,(dis[x]+w,y))\n",
    "        ans=0\n",
    "        for x in dis:\n",
    "            if x<=maxMoves:\n",
    "                ans+=1\n",
    "        #如何避免重复计算？\n",
    "        for x,y,w in edges:\n",
    "            dx,dy=dis[x],dis[y]\n",
    "            #下标从1开始一直到w\n",
    "            farx=min(maxMoves-dx,w) if dx<maxMoves else 0\n",
    "            fary=min(maxMoves-dy,w) if dy<maxMoves else 0\n",
    "            ans+=min(farx+fary,w)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            g[u].append((v,cnt + 1))\n",
    "            g[v].append((u,cnt + 1))\n",
    "        q = [(0,0)]\n",
    "        dis = [inf]*n\n",
    "        dis[0] = 0\n",
    "        while q:\n",
    "            d,i = heappop(q)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j,w in g[i]:\n",
    "                new_d = dis[i] + w\n",
    "                #print(new_d,dis[j])\n",
    "                if new_d < dis[j]:\n",
    "                    dis[j] = new_d\n",
    "                    heappush(q,(new_d,j))\n",
    "        \n",
    "        ans = sum(d <= maxMoves for d in dis)\n",
    "        for u,v,cnt in edges:\n",
    "            a,b = max(maxMoves - dis[u],0),max(maxMoves - dis[v],0)\n",
    "            ans += min(a + b,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "                    # total += (maxMoves - dist[u])\n",
    "                    # total += (maxMoves - dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if u > maxMoves:\n",
    "                break\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            count += 1 if dist[i] <= maxMoves else 0\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for e in edges:\n",
    "            print(e)\n",
    "            ### 注意有关图的声明与处理要灵活应变！！！\n",
    "            g[e[0]].append([e[1],e[2]+1])\n",
    "            g[e[1]].append([e[0],e[2]+1])\n",
    "        #print(g)\n",
    "        #visit = defaultdict()\n",
    "        q = []\n",
    "        q.append((0,0))\n",
    "        dist = [0] + [inf] * (n)\n",
    "        ###这段的本质是求两点之间的最短路径！！！\n",
    "        while q:\n",
    "            ### 注意可以从小到大求解！！！利用小根堆！！！因为优先排序是根据第一个元素，所以此处将值放在第一位，这在后续的处理中要小心！！！别与构图g弄混！！！\n",
    "            ###注意！！！！！！headpop必须对应的是列表！！！list!!!\n",
    "            hp, cur = heappop(q)\n",
    "            ### 注意看好这个图对应的是什么，节点在前还是值在前，不要与q中的排列布局弄混！！！\n",
    "            for nxt,hpp in g[cur]:\n",
    "                ### 此处相当于找最短路径，根本不涉及maxMoves的判断与限制，因此在后期的答案的处理中要涉及此限制！\n",
    "                if hp + hpp < dist[nxt]:\n",
    "                    dist[nxt] = hp + hpp\n",
    "                    ###  此处要小心注意！！\n",
    "                    q.append((hp + hpp, nxt))\n",
    "        ### 巧用python相关函数\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for e in edges:\n",
    "            ### 这是从不同方向进行考虑！\n",
    "            u = min(e[2], max(0,maxMoves - dist[e[0]]))\n",
    "            v = min(e[2], max(0,maxMoves - dist[e[1]]))\n",
    "            ans += min(e[2], u + v)\n",
    "        \n",
    "        #别最后忘了return！！！\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, c in edges:\n",
    "            dct[i].append([j, c+1])\n",
    "            dct[j].append([i, c+1])\n",
    "        \n",
    "        dis  =Dijkstra().get_dijkstra_result(dct, 0)\n",
    "        \n",
    "        ans = sum(dis[i]<=maxMoves for i in range(n))\n",
    "        for i, j, c in edges:\n",
    "            if c:\n",
    "                if dis[i] <= maxMoves:\n",
    "                    left = ac_min(maxMoves - dis[i], c)\n",
    "                else:\n",
    "                    left = 0\n",
    "                \n",
    "                if dis[j] <= maxMoves:\n",
    "                    right = ac_min(maxMoves - dis[j], c)\n",
    "                else:\n",
    "                    right = 0\n",
    "                \n",
    "                if left+right<=c:\n",
    "                    ans += left+right\n",
    "                else:\n",
    "                    ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u,v,cnt in edges:\n",
    "            graph[u].append((v,1+cnt))\n",
    "            graph[v].append((u,1+cnt))\n",
    "        \n",
    "        queue = [(0,0)]\n",
    "        dist = [float('inf')]*n\n",
    "        dist[0] = 0\n",
    "        while queue:\n",
    "            dis,x = heapq.heappop(queue)\n",
    "            if dist[x]<dis:\n",
    "                continue\n",
    "            for nextN,nextD in graph[x]:\n",
    "                if dis+nextD < dist[nextN]:\n",
    "                    dist[nextN] = dis + nextD\n",
    "                    heapq.heappush(queue, (dist[nextN],nextN))\n",
    "            pass\n",
    "        \n",
    "        total = 0\n",
    "        for i in range(n):\n",
    "            if dist[i]<=maxMoves:\n",
    "                total += 1\n",
    "        for u,v,cnt in edges:\n",
    "            if dist[u]==float('inf') or dist[v]==float('inf'):\n",
    "                pass\n",
    "            elif dist[u]>maxMoves and dist[v]>maxMoves:\n",
    "                pass\n",
    "            elif dist[u]>maxMoves:\n",
    "                total += (maxMoves - dist[v])\n",
    "            elif dist[v]>maxMoves:\n",
    "                total += (maxMoves - dist[u])\n",
    "            else:\n",
    "                if abs(dist[u]-dist[v])==1+cnt:\n",
    "                    total += cnt\n",
    "                else:\n",
    "                    total += min(cnt, maxMoves*2-dist[u]-dist[v])\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b, c in edges:\n",
    "            graph[a].append([b, c + 1])\n",
    "            graph[b].append([a, c + 1])\n",
    "        dis = [float('inf')] * n \n",
    "        dis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei, cost in graph[cur]:\n",
    "                if dis[nei] > dis[cur] + cost:\n",
    "                    dis[nei] = dis[cur] + cost \n",
    "                    queue.append(nei)\n",
    "        res = 0\n",
    "        for a, b, c in edges:\n",
    "            res += min(c, max(maxMoves - dis[a], 0) + max(maxMoves - dis[b], 0))\n",
    "        for node in range(n):\n",
    "            if dis[node] <= maxMoves:\n",
    "                res += 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(dict)\n",
    "        for x, y, c in edges:\n",
    "            g[x][y] = g[y][x] = c\n",
    "        dist = [-1] * n\n",
    "        dist[0] = maxMoves\n",
    "        h = [(-maxMoves, 0)]\n",
    "        ans = 0\n",
    "        while h:\n",
    "            v, x = heappop(h)\n",
    "            v *= -1\n",
    "            if v < dist[x]: continue\n",
    "            ans += 1\n",
    "            for y, c in g[x].items():\n",
    "                if v >= c + 1:\n",
    "                    ans += c\n",
    "                    if v - c - 1 > dist[y]:\n",
    "                        dist[y] = v - c - 1\n",
    "                        heappush(h, (c + 1 - v, y))\n",
    "                    g[y][x] = 0\n",
    "                elif v < c + 1:\n",
    "                    ans += v\n",
    "                    g[y][x] -= v\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "class Dijkstra:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_dijkstra_result(dct: List[List[int]], src: int) -> List[float]:\n",
    "        # 模板: Dijkstra求最短路，变成负数求可以求最长路（还是正权值）\n",
    "        n = len(dct)\n",
    "        dis = [inf]*n\n",
    "        stack = [[0, src]]\n",
    "        dis[src] = 0\n",
    "\n",
    "        while stack:\n",
    "            d, i = heapq.heappop(stack)\n",
    "            if dis[i] < d:\n",
    "                continue\n",
    "            for j, w in dct[i]:\n",
    "                dj = w + d\n",
    "                if dj < dis[j]:\n",
    "                    dis[j] = dj\n",
    "                    heapq.heappush(stack, [dj, j])\n",
    "        return dis\n",
    "    \n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j, c in edges:\n",
    "            dct[i].append([j, c+1])\n",
    "            dct[j].append([i, c+1])\n",
    "        \n",
    "        dis  =Dijkstra().get_dijkstra_result(dct, 0)\n",
    "        \n",
    "        ans = sum(dis[i] <= maxMoves for i in range(n))\n",
    "        for i, j, c in edges:\n",
    "            if c:\n",
    "                if dis[i] <= maxMoves:\n",
    "                    a, b = maxMoves - dis[i], c\n",
    "                    left = a if a < b else b\n",
    "                else:\n",
    "                    left = 0\n",
    "                \n",
    "                if dis[j] <= maxMoves:\n",
    "                    a, b = maxMoves - dis[j], c\n",
    "                    right = a if a < b else b\n",
    "                else:\n",
    "                    right = 0\n",
    "                \n",
    "                if left+right <= c:\n",
    "                    ans += left+right\n",
    "                else:\n",
    "                    ans += c\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            graph[u].append((v, nodes+1))\n",
    "            graph[v].append((u, nodes+1))\n",
    "        \n",
    "        dist = [inf]*n\n",
    "        seen = set()\n",
    "        dist[0] = 0\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            dst, u = heapq.heappop(q)\n",
    "            if u in seen:\n",
    "                continue\n",
    "            seen.add(u)\n",
    "            for v, distance in graph[u]:\n",
    "                if dist[u]+distance < dist[v]:\n",
    "                    dist[v] = dist[u]+distance\n",
    "                    heapq.heappush(q, (dist[v], v))\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if dist[i] <=maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, edge in edges:\n",
    "            t1 = max(0, maxMoves-dist[u])\n",
    "            t2 = max(0, maxMoves-dist[v])\n",
    "            ans += min(edge, t1+t2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for e in edges:\n",
    "            print(e)\n",
    "            ### 注意有关图的声明与处理要灵活应变！！！\n",
    "            g[e[0]].append([e[1],e[2]+1])\n",
    "            g[e[1]].append([e[0],e[2]+1])\n",
    "        #print(g)\n",
    "        #visit = defaultdict()\n",
    "        q = []\n",
    "        q.append((0,0))\n",
    "        dist = [0] + [inf] * (n-1)\n",
    "        ###这段的本质是求两点之间的最短路径！！！\n",
    "        while q:\n",
    "            ### 注意可以从小到大求解！！！利用小根堆！！！因为优先排序是根据第一个元素，所以此处将值放在第一位，这在后续的处理中要小心！！！别与构图g弄混！！！\n",
    "            ###注意！！！！！！headpop必须对应的是列表！！！list!!!\n",
    "            hp, cur = heappop(q)\n",
    "            ### 注意看好这个图对应的是什么，节点在前还是值在前，不要与q中的排列布局弄混！！！\n",
    "            for nxt,hpp in g[cur]:\n",
    "                ### 此处相当于找最短路径，根本不涉及maxMoves的判断与限制，因此在后期的答案的处理中要涉及此限制！\n",
    "                if hp + hpp < dist[nxt]:\n",
    "                    dist[nxt] = hp + hpp\n",
    "                    ###  此处要小心注意！！\n",
    "                    q.append((hp + hpp, nxt))\n",
    "        ### 巧用python相关函数\n",
    "        ans = sum(d <= maxMoves for d in dist)\n",
    "        for e in edges:\n",
    "            ### 这是从不同方向进行考虑！\n",
    "            u = min(e[2], max(0,maxMoves - dist[e[0]]))\n",
    "            v = min(e[2], max(0,maxMoves - dist[e[1]]))\n",
    "            ans += min(e[2], u + v)\n",
    "        \n",
    "        #别最后忘了return！！！\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        for _ in range(n):\n",
    "            x = -1\n",
    "            for i in range(n):\n",
    "                if not vis[i] and (x == -1 or dist[i] < dist[x]):\n",
    "                    x = i\n",
    "            \n",
    "            vis[x] = True\n",
    "            for y, q in enumerate(g[x]):\n",
    "                \n",
    "                if dist[x] + q[1] < dist[q[0]]:\n",
    "                    dist[q[0]] = dist[x] + q[1]\n",
    "        print(dist)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def build_graph(self, edges: List[List[int]]) -> defaultdict:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, w in edges:\n",
    "            graph[u].append([v, w + 1])\n",
    "            graph[v].append([u, w + 1])\n",
    "        return graph\n",
    "\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = self.build_graph(edges)\n",
    "\n",
    "        dist = [math.inf] * n\n",
    "        heap = [(0, 0)]\n",
    "        while heap:\n",
    "            (cost, u) = heapq.heappop(heap)\n",
    "            if not math.isinf(dist[u]):\n",
    "                continue\n",
    "            dist[u] = cost\n",
    "            for v, w in graph[u]:\n",
    "                if not math.isinf(dist[v]):\n",
    "                    continue\n",
    "                heapq.heappush(heap, (cost+w, v))\n",
    "\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            count += 1 if dist[i] <= maxMoves else 0\n",
    "        for u, v, w in edges:\n",
    "            count += min(max(maxMoves - dist[u], 0) + max(maxMoves - dist[v], 0), w)\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        # 获取所有点的最短路路径\n",
    "        # 查看所有的双向边，根据边的子节点数和两个端点的最短距离以及maxMoves判断边上有多少子节点可以访问\n",
    "        can_move = {}\n",
    "        visit_edge = set()\n",
    "        min_distance = {}\n",
    "        for edge in edges:\n",
    "            if edge[0] not in can_move.keys():\n",
    "                can_move[edge[0]] = {}\n",
    "            can_move[edge[0]][edge[1]] = edge[2]\n",
    "            if edge[1] not in can_move.keys():\n",
    "                can_move[edge[1]] = {}\n",
    "            can_move[edge[1]][edge[0]] = edge[2]\n",
    "        \n",
    "        queue = [{\"point\": 0, \"min_dis\": 0}]\n",
    "        for i in range(1, n):\n",
    "            queue.append({\"point\": i, \"min_dis\": 10**20})\n",
    "        get_min_dis = set()\n",
    "        while queue:\n",
    "            # 找到最短路径节点\n",
    "            min_dis = queue[0][\"min_dis\"]\n",
    "            min_pos = 0\n",
    "            for i in range(len(queue)):\n",
    "                if queue[i][\"min_dis\"] < min_dis:\n",
    "                    min_dis = queue[i][\"min_dis\"]\n",
    "                    min_pos = i\n",
    "            min_point = queue[min_pos][\"point\"]\n",
    "            min_distance[min_point] = min_dis\n",
    "            queue.pop(min_pos)\n",
    "            # 更新节点信息\n",
    "            for i in range(len(queue)):\n",
    "                if min_point in can_move and queue[i][\"point\"] in can_move[min_point] and queue[i][\"min_dis\"] > min_dis + can_move[min_point][queue[i][\"point\"]] + 1:\n",
    "                    queue[i][\"min_dis\"] = min_dis + can_move[min_point][queue[i][\"point\"]] + 1\n",
    "        res = 0\n",
    "        for p in min_distance:\n",
    "            if min_distance[p] != 10**20 and min_distance[p] <= maxMoves:\n",
    "                res += 1\n",
    "        for edge in edges:\n",
    "            if maxMoves - min_distance[edge[0]] >= edge[2] or maxMoves - min_distance[edge[1]] >= edge[2]:\n",
    "                res += edge[2]\n",
    "            elif maxMoves - min_distance[edge[0]] + maxMoves - min_distance[edge[1]] >= edge[2]:\n",
    "                res += edge[2]\n",
    "            else:\n",
    "                if maxMoves > min_distance[edge[0]]:\n",
    "                    res += maxMoves - min_distance[edge[0]]\n",
    "                if maxMoves > min_distance[edge[1]]:\n",
    "                    res += maxMoves - min_distance[edge[1]]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        start = 0\n",
    "        # 如何通过heapq来优化dijkstra算法\n",
    "        import heapq\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heapq.heappop(h)\n",
    "            # if d > dist[x]:\n",
    "            #     continue\n",
    "            \n",
    "            for y, wt in g[x]:\n",
    "                newd = dist[x] + wt\n",
    "                if newd < dist[y]:\n",
    "                    dist[y] = newd\n",
    "                    heapq.heappush(h, (dist[y], y))\n",
    "        \n",
    "        print(dist)\n",
    "        ans = 0\n",
    "\n",
    "        # 计算最短路的意义，求出最短路来，就可以知道有多少个点可以算到ans里面\n",
    "        # 计算每条边上，能有多少个点\n",
    "        # 这个的要点是从起点出发\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            g[u].append((v, cnt + 1))\n",
    "            g[v].append((u, cnt + 1))  # 建图\n",
    "        print(g)\n",
    "        dist = [inf] * n\n",
    "        vis = [False] * n\n",
    "        dist[0] = 0\n",
    "\n",
    "        start = 0\n",
    "        # 如何通过heapq来优化dijkstra算法\n",
    "        import heapq\n",
    "        h = [(0, start)]\n",
    "        while h:\n",
    "            d, x = heapq.heappop(h)\n",
    "            if d > dist[x]:\n",
    "                continue\n",
    "            \n",
    "            for y, wt in g[x]:\n",
    "                newd = dist[x] + wt\n",
    "                if newd < dist[y]:\n",
    "                    dist[y] = newd\n",
    "                    heapq.heappush(h, (dist[y], y))\n",
    "        \n",
    "        print(dist)\n",
    "        ans = 0\n",
    "\n",
    "        # 计算最短路的意义，求出最短路来，就可以知道有多少个点可以算到ans里面\n",
    "        # 计算每条边上，能有多少个点\n",
    "        # 这个的要点是从起点出发\n",
    "        for i in range(n):\n",
    "            if dist[i] <= maxMoves:\n",
    "                ans += 1\n",
    "        for u, v, cnt in edges:\n",
    "            a = max(maxMoves - dist[u], 0)\n",
    "            b = max(maxMoves - dist[v], 0)\n",
    "            \n",
    "            ans += min(a + b, cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        G = [[] for _ in range(n)]\n",
    "        for u,v,w in edges:\n",
    "            G[u].append([v,w])\n",
    "            G[v].append([u,w])\n",
    "        c = Counter()\n",
    "\n",
    "        # dijkstra\n",
    "        dist = [math.inf] * n\n",
    "        dist[0] = 0\n",
    "        h = [(0,0)]\n",
    "        while h:\n",
    "            di, i = heappop(h)\n",
    "            if di != dist[i]: continue\n",
    "            if di > maxMoves: break\n",
    "            for j,w in G[i]:\n",
    "                if di + w+1 < dist[j]:\n",
    "                    dist[j] = di + w+1\n",
    "                    heappush(h, (dist[j], j))\n",
    "        \n",
    "        ans = 0\n",
    "        for i,di in enumerate(dist):\n",
    "            if di > maxMoves: continue\n",
    "            ans += 1\n",
    "            x = maxMoves - di\n",
    "            for j,w in G[i]:\n",
    "                c[(i,j)] = x\n",
    "\n",
    "        for i,j,w in edges:\n",
    "            ans += min(w, c[(i,j)] + c[(j,i)])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        connects = collections.defaultdict(dict)\n",
    "        for s, e, c in edges:\n",
    "            connects[s][e] = c\n",
    "            connects[e][s] = c\n",
    "        stack, visited, ans = [[0, 0]], set(), 0\n",
    "        cnts = {}\n",
    "        while stack:\n",
    "            val, idx = heapq.heappop(stack)\n",
    "            if not idx in visited:\n",
    "                visited.add(idx)\n",
    "                ans += 1\n",
    "                for nexti in connects[idx]:\n",
    "                    c = connects[idx][nexti]\n",
    "                    cnts[(idx, nexti)] = min(maxMoves - val, c)\n",
    "                    if maxMoves - val >=  c + 1 and not nexti in visited:\n",
    "                        heapq.heappush(stack, [val + 1 + c, nexti])\n",
    "        for i, j in cnts:\n",
    "            if i > j and (j, i) in cnts: continue\n",
    "            tmp = cnts[(i, j)]\n",
    "            if (j, i) in cnts: tmp += cnts[(j, i)]\n",
    "            ans += min(tmp, connects[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from collections import deque\r\n",
    "import heapq\r\n",
    "class Solution:\r\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\r\n",
    "\r\n",
    "        graph=[[] for _ in range(n)]\r\n",
    "        # edge_vis={}\r\n",
    "        for x,y,d in edges:\r\n",
    "            graph[x].append([y,d])\r\n",
    "            graph[y].append([x,d])\r\n",
    "        \r\n",
    "        q=[[0,0]]\r\n",
    "        ret=0\r\n",
    "        vis=set()\r\n",
    "        # dis=[0]*n\r\n",
    "        used={}\r\n",
    "        while q:\r\n",
    "            step,x =heapq.heappop(q)\r\n",
    "            if x in vis:\r\n",
    "                continue\r\n",
    "            vis.add(x)\r\n",
    "            ret+=1\r\n",
    "            for y,nodes in graph[x]:\r\n",
    "                if step+1+nodes<=maxMoves and y not in vis:\r\n",
    "                    # ret+=1\r\n",
    "                    heapq.heappush(q,[step+1+nodes,y])\r\n",
    "                used[(x,y)]=max(0,maxMoves-step)\r\n",
    "        for x,y,nodes in edges:\r\n",
    "            ret+=min(nodes,used.get((x,y),0)+used.get((y,x),0))\r\n",
    "        return ret\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        adList = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            adList[u].append([v, nodes])\n",
    "            adList[v].append([u, nodes])\n",
    "        used = {}\n",
    "        visited = set()\n",
    "        reachableNodes = 0\n",
    "        pq = [[0, 0]]\n",
    "\n",
    "        while pq and pq[0][0] <= maxMoves:\n",
    "            step, u = heapq.heappop(pq)\n",
    "            if u in visited:\n",
    "                continue\n",
    "            visited.add(u)\n",
    "            reachableNodes += 1\n",
    "            for v, nodes in adList[u]:\n",
    "                if nodes + step + 1 <= maxMoves and v not in visited:\n",
    "                    heappush(pq, [nodes + step + 1, v])\n",
    "                used[(u, v)] = min(nodes, maxMoves - step)\n",
    "\n",
    "        for u, v, nodes in edges:\n",
    "            reachableNodes += min(nodes, used.get((u, v), 0) + used.get((v, u), 0))\n",
    "        return reachableNodes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u, v, cnt in edges:\n",
    "            graph[u].append((v, cnt))\n",
    "            graph[v].append((u, cnt))\n",
    "\n",
    "        ans = 0\n",
    "        edge_max = collections.defaultdict(int)\n",
    "        heap = [(0, 0)]\n",
    "        min_dist = [math.inf] * n\n",
    "        while heap:\n",
    "            d, cur = heapq.heappop(heap)\n",
    "            if d >= min_dist[cur]:\n",
    "                continue\n",
    "            min_dist[cur] = d\n",
    "            ans += 1\n",
    "            for nxt, cnt in graph[cur]:\n",
    "                nd = d + cnt + 1\n",
    "                if nd <= maxMoves and nd < min_dist[nxt]:\n",
    "                    heapq.heappush(heap, (nd, nxt))\n",
    "                edge_max[(cur, nxt)] = max(edge_max[(cur, nxt)], maxMoves - d)\n",
    "\n",
    "        for u, v, cnt in edges:\n",
    "            ans += min(cnt, edge_max[(u, v)] + edge_max[(v, u)])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:\n",
    "        adList = defaultdict(list)\n",
    "        for u, v, nodes in edges:\n",
    "            adList[u].append([v, nodes])\n",
    "            adList[v].append([u, nodes])\n",
    "        used = {}\n",
    "        visited = set()\n",
    "        reachableNodes = 0\n",
    "        pq = [[0, 0]]\n",
    "\n",
    "        while pq and pq[0][0] <= maxMoves:\n",
    "            step, u = heapq.heappop(pq)\n",
    "            if u in visited:\n",
    "                continue\n",
    "            visited.add(u)\n",
    "            reachableNodes += 1\n",
    "            for v, nodes in adList[u]:\n",
    "                if nodes + step + 1 <= maxMoves and v not in visited:\n",
    "                    heappush(pq, [nodes + step + 1, v])\n",
    "                used[(u, v)] = min(nodes, maxMoves - step)\n",
    "\n",
    "        for u, v, nodes in edges:\n",
    "            reachableNodes += min(nodes, used.get((u, v), 0) + used.get((v, u), 0))\n",
    "        return reachableNodes"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
